package 动态规划;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/10 15:35
 */
public class leetcode1223掷筛子模拟 {


        /*
         这个 看下 , 怎么 优化, (进行 一个 斜率的优化)
         这个优化有点 难顶
         ,主要是, 递归函数的 参数 有点太多了!等后面 优化一下!
         */









        /*
         这个题远比 你想的有意思！（有点像另类的 动态规划里面的 ，那种动态规划的思想了）
          这个 思想 ，又有点 特殊， 仔细品味 一下： ( 因为 这里 面 是 全排列)
         这里面有很多的 ，知识，
        这个  记忆化搜索 函数 直接 是真的 能悟到 很多的 东西
         */
        public int MOD = 1000000007;

        public int recursion(int n,int count ,int last,int nums[],int dp[][][]){
                if(n == 0){
                        return 1;
                }
                if(dp[n][count][last] != -1){
                        return dp[n][count][last];
                }
                long ans = 0;
                for(int  i = 0;i < 6;i++){
                        // 等下体会一下 这样写的 好处！
                        if(last != i){
                                ans += recursion(n - 1,1,i,nums,dp);
                        }
                        else if (count != nums[last]){
                                ans += recursion(n - 1,count + 1,last,nums,dp);
                        }
                }
                return dp[n][count][last] = (int) (ans % MOD);
        }
        public int solution(int n,int rollMax[]){
                int dp[][][] = new int[n + 1][15][6];
                /*
                  可以 直接声明 成 引用 类型的 数组， 反正 都是  4 个字节
                  而且 最关键 的一个点 在于， Integer [] 这种 不需要 初始化 -1
                  这种操作, 可以 直接 进行 判断 null 值. 来 判断是否 计算过 该过程!
                 */
                for(int [][] temp1 : dp){
                        for(int [] temp2 : temp1){
                                Arrays.fill(temp2, -1);
                        }
                }
                return recursion(n,0,0,rollMax,dp);
        }

        /*
         注意  灵神 这种写法
         其实他这种写法, 你是 明白 什么意思的
         但是 该题 , 具有 特殊性 (递归 内部的 for 循环 是个 全排列 这种. 就有些 特殊了!)
         */
        class Solution {
                private static final long MOD = (long) 1e9 + 7;
                private int[] rollMax;
                private int[][][] cache;

                public int dieSimulator(int n, int[] rollMax) {
                        this.rollMax = rollMax;
                        int m = rollMax.length;
                        cache = new int[n][m][15];
                        for (int i = 0; i < n; i++)
                                for (int j = 0; j < m; ++j)
                                        Arrays.fill(cache[i][j], -1); // -1 表示没有访问过
                        long ans = 0;
                        /*
                         这里 处理方式, 就是 每一次 只 能 求 一个.
                         如果 按照 这种处理方式的, 那 就是 属于 另类的动态规划
                         */
                        for (int j = 0; j < m; ++j)
                                ans += dfs(n - 1, j, rollMax[j] - 1);
                        return (int) (ans % MOD);
                }

                private int dfs(int i, int last, int left) {
                        if (i == 0) return 1;
                        if (cache[i][last][left] >= 0) return cache[i][last][left];
                        long res = 0;
                        for (int j = 0; j < rollMax.length; ++j)
                                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                                else if (left > 0) res += dfs(i - 1, j, left - 1);
                        return cache[i][last][left] = (int) (res % MOD);
                }
        }


}
